package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 236. 二叉树的最近公共祖先
 *
 * @author fy
 * @date 2022/3/30 15:28
 */
public class Solution236 {

    // 记录最近公共祖先
    private TreeNode parent = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return parent;
        }
        dfs(root, p, q);
        return parent;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        // 查看p或者q是否在左子树
        boolean inLeft = dfs(root.left, p, q);
        // 查看p或者q是否在右子树
        boolean inRight = dfs(root.right, p, q);
        // 1. 如果分别在左右两颗子树, 那当前root节点就是公共祖先
        // 2. 当前p或q有一个节点是root, 另一个在左或者右子树, 那当前节点就是公共祖先
        // 3. 一直递归直到最里层, 找到最近公共祖先
        if ((inLeft && inRight) ||
                ((root.val == p.val || root.val == q.val) && (inLeft || inRight))) {
            this.parent = root;
        }
        // 已在左或者右子树或者当前就是p或q, 那么当前树必定包含p或者q
        return inLeft || inRight || (root.val == p.val || root.val == q.val);
    }

}
